1. Field of the Invention
The present invention relates to a device and a method for encoding multivalue image data.
2. Description of the Related Art
Recently, personal computers (hereinafter, “PC”), digital cameras etc. are widely available in general market. Due to this, color images such as color photographs, color pictures that are mainly graphics are increasingly output using an image forming apparatus. In the image forming apparatus such as a printer, image data that is transmitted from a PC is stored in a temporary memory to form an image. However, compared to binary image data that expresses a black and white image, a significantly large capacity is necessitated for multivalue image data that expresses a color image. Due to this, a memory of a large capacity needs to be mounted in the image forming apparatus for processing a large amount of the multivalue image data without putting on hold a transmission from the external device such as the PC, thus increasing the cost. Thus, it is desirable to reduce a memory capacity by ensuring that a plurality of the multivalue image data, which are sequentially transmitted from the external device, are stored in the temporary memory while being compressed by encoding, and ensuring that the stored encoded multivalue image data are sequentially decoded at the time of an image forming process.
In a method that is well known as a method to encode the image data, the multivalue image data is converted into a frequency component by using an orthogonal transformation such as discreet cosine transform (DCT) and a conversion coefficient is quantized. For example, joint photographic experts group (JPEG), which is standardized by International Telecommunications Union-Telecommunications Standardization Division (IUT-T) and International Organization for Standardization (ISO), is also one of the methods to encode the image data.
However, in the method that quantizes the conversion coefficient of the frequency component of the image data, eliminating a high frequency component results in irreversible compressed image data that includes image deterioration such as mosquito noise. The image deterioration noticeably occurs in the color image such as the graphics that include a sharp hue change. Due to this, the multivalue image data, which mainly includes the graphics, cannot be compressed to an image quality that is the same or nearly the same as the image quality of the original image.
A run length method is known as another method for encoding the image data. In the run length method, in a pixel column formed of a plurality of pixels, an isochromatic continuous pixel cluster, which includes multiple pixels that continue isochromatically with respect to each other, is converted into a code that indicates a run and a length of the isochromatic continuous pixel cluster. For example, in the pixel column of the binary image data, if the pixels are aligned in a sequence of “black, black, black, black, black, black, black, white, white, white, black, white, white, white, white”, the pixel cluster is substituted by a code “7314”. Because the binary image data includes only the two colors of black and white, by deciding a color that is treated as an initial run and using a number that indicates the run length, the pixel column can be expressed. For example, the code “7314” indicates the pixel column in which black is prior decided to be treated as the initial run. If white is prior decided to be treated as the initial run, the pixel column can be expressed as “07314”. However, in the multivalue image data, apart from run data that indicates the respective run length of each run, color data is also necessitated that indicates the respective color data of each run.
A capacity of the image data can be significantly compressed by using the run length method for the image that includes a large number of pixels of the same color or the image that includes a large number of white spaces. Further, irreversible compressed image data can be obtained that does not differ from the original image. A method which is disclosed in Japanese Patent Application Laid-open No. 2005-27081 is known as an image data encoding method that incorporates the run length method.
However, when using the run length method to encode the multivalue image data, which mainly includes the graphics that include abundant hue change, a data capacity after encoding cannot be significantly reduced compared to an original data capacity. The drawback is due to the following two reasons.
Firstly, in the multivalue image data that includes abundant hue change, a run does not continue for long. To be specific, in most of the recent data processing units such as computers, the color image is expressed as a full color image. In the full color image, brightness of the three primary colors of red (R), green (G), and blue (B) (or yellow (Y), magenta (M), and cyan (C)) is divided into 256 grayscales respectively. Thus, a total of 16777216 types of colors can be expressed. If the multivalue image data, which includes abundant hue change, is subjected to such a full color expression, even a marginal difference of color that is nearly invisible causes the run to end. Due to this, a number of runs that are included in run data after encoding become extremely large, thus hampering a reduction of the data capacity.
Secondly, in the data capacity after encoding, a percentage occupied by the color data mentioned earlier increases. For example, in the full color expression of 16777216 colors, because eight bits are needed for notation of R, G, and B (or Y, M, and C) respectively, one color necessitates a data capacity of 24 bits. Arranging such a data capacity corresponding to each individual run hampers a reduction of the data capacity.